package leetcode;

// 给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
//返回 s 所有可能的分割方案

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class problems_131 {

    public static void main(String[] arge) {
        System.out.println(new Solution().partition("abbab"));
    }

    static class Solution {
        public List<List<String>> partition(String s) {
            List<List<String>> ret = new ArrayList<>();
            if(null == s || s.length() == 0) return ret;
            Deque<String> deque = new ArrayDeque<>();
            backtracking(s, 0, s.length(), deque, ret);
            return ret;
        }
        /**
         * 判断文字
         * 判断的是正途的一部分
         */
        private void backtracking(String txt, int start, int len, Deque<String> deque, List<List<String>> ret) {
            // 如果指针已经指到最后，判断成功，返回
            if (start == len) {
                ret.add(new ArrayList<>(deque));
                return;
            }
            // 遍历对象
            for (int i = start; i < len; i++) {
                // 比较前半部分
                if (!isHuiWen(txt, start, i + 1)) {
                    continue;
                }
                // 前半是回文，则追加前半
                deque.add(txt.substring(start, i + 1));
                // 然后，
                backtracking(txt, i + 1, len, deque, ret);
                deque.removeLast();
            }
        }

        /**
         * 回文字符串判断
         */
        private boolean isHuiWen(String s, int i, int len) {
            if (i == len || Math.abs(len - i) <= 1) return true;
            int helf = Math.abs(len - i) / 2;
            for (int index = 0; index < helf; index++) {
                if (s.charAt(i + index) != s.charAt(len - 1 - index)) {
                    return false;
                }
            }
            return true;
        }
    }
}
